Recent improvements in their spatial and data resolution capabilities have made digital image processing systems attractive for a number of photoprocessing applications. In still image photography, for example, once an image (such as a multilevel grey scale image captured on photographic film or a high resolution digital camera) has been digitized and stored in an attendant data base, it is optimized for reproduction by a variety of reproduction devices. Unfortunately, a number of digital image output devices, such as dot matrix printers, laser printers, etc., possess only binary output capability; namely, they can print only two tone (e.g. black and white) images. As a result, in order to reproduce a continuous tone or grey scale image by way of such a device, the grey scale levels of the original digital image must be encoded or `half-toned` into binary values (e.g. 0=black and 1=white), from which respective pixel representative signals are produced.
Because the reduced digital code resolution of the binary values constitutes a significant reduction in image content (loss of grey scale code width), the mechanism through which the half-toning of the original digital image takes place should be designed so that the binary image takes on the appearance of an image having grey scale or continuous tone qualities.
Such a half-toning mechanism may be represented spatially as `dithering` mask M[A][B], or array of A rows and B columns, with entries in the M[i][j] array being greater than or equal to 0.0 and less than 1.0, where [i][j] denotes a pixel location. Also, [i] is greater than or equal to 0 and less than or equal to A, and [j] is greater than or equal to 0 and less than or equal to B. Respective grey scale values of a corresponding array of pixels of the original digital image are compared with entries in the mask. Depending upon whether a respective grey scale value of the digital image is larger than a threshold value of an associated matrix location of the mask, as effectively spatially superimposed upon the digital image, the grey scale value will be converted to a half-tone value of either zero or one.
Thus, when the half-toning mask M is applied to a grey scale-valued pixel of an original image, a half-toned output value H[i][j] may be defined in accordance with the mask M by the condition:
if the grey-scale value at [I][J] is greater than or equal to M[i%A][j%B], then output H[i][j]=0 (black); otherwise output H[i][j]=1 (white),
where i%A denotes the remainder of the integer division i/A, and j%B denotes the remainder of the integer division j/B.
One conventionally employed half-toning mechanism employs a white noise source, such as a pseudo-random number distribution function, to establish the entries of the mask. Because the spectral power of white noise is equally strong at every frequency, the half-toned image tends to contain low frequency, visually disturbing artifacts. One proposal to solve this problem and provide a more desirable masking technique, is described by B. E. Bayer in an article entitled "An optimum method for two-level rendition of continuous-tone pictures," IEEE Int. Conf. Commun., 1:11-15 (1973). The Bayer mechanism takes advantage of the reduced sensitivity of the human visual system to very high frequency signals, by using a family of fixed half-tone masks of sizes 2.sup.m .times.2.sup.m and 2.sup.m+1 .times.2.sup.m, which employ an optimal thresholding criterion involving low spectral power at low frequencies.
Unfortunately, the generation of conventional masks is often computationally intensive and, depending upon image requirements, particularly in the case of very high resolution images (e.g. 1024.times.2048 pixel arrays), the masks themselves may be of such a size as to require an extraordinarily large memory space within which to store the threshold values.